COMMENT ⊗   VALID 00005 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input acphdr
C00003 00003	% Appendix B (Index to notations)	*
C00023 00004	\eject
C00031 00005
C00046 ENDMK
C⊗;
\input acphdr
\runninglefthead{ARITHMETIC---FIRST PROOFS $\copyright$ 1978}
\runningrighthead{ARITHMETIC---FIRST PROOFS $\copyright$ 1978}
\section{4.x}
\setcount0 701
\tenpoint
% Appendix B (Index to notations)	*
\lineskip0pt
\def\medlp{\mathopen{\vcenter{\hjust{\:@\char'20}}}}
\def\medrp{\mathclose{\vcenter{\hjust{\:@\char'21}}}}
\def\¬{\lower 2.5pt\vjust to 12pt{}}
\def\\{\noalign{\vfill}}
\def\+#1{\baselineskip12pt\lower 12pt\hjust to 192pt{\¬#1\¬}}
\def\2#1 #2{$\vtop{\baselineskip20pt\hjust{#1}
\hjust to 192pt{\ctr{$#2$}}}$}
\def\∨#1{\lower 12pt\hjust{#1}}
\def\∪#1{\lower 20pt\hjust{#1}}
\runningrighthead{INDEX TO NOTATIONS}
\section{}
\eject % eject the previous page
\runninglefthead{APPENDIX B}
\acpmark{\chd}{\csec}
\titlepage\corners
\vskip 1cm plus 30pt minus 10pt
\hjust{\def\\{\hskip 1pt}\:=A\\P\\P\\E\\N\\D\\I\\X\hskip 10pt B}
\vfill
\rjustline{\:;INDEX TO NOTATIONS}
\vfill
\tenpoint\noindent In the following formulas, letters that are not further
qualified have the following significance:
$$\vjust{\halign{$\hfill#$⊗\qquad#\hfill\cr
j,k⊗integer-valued arithmetic expression\cr
m,n⊗nonnegative integer-valued arithmetic expression\cr
x,y,z⊗real-valued arithmetic expression\cr
f⊗real-valued function\cr}}$$

\vskip 6pt
\hjust to size{\hskip 8pc\vrule height 300pt\hfill\vrule\hskip 4pc}
\vskip-300pt
\vjust to 300pt{
\hjust to size{\bf\hfill\hjust to 4pc{\9\ctr{Section}}}
\hjust to size{\bf\hjust to 8pc{\ctr{Formal symbolism}\9}\hfill
Meaning\hfill\hjust to 4pc{\9\ctr{reference}}}
\vskip3pt\hrule\vskip6pt
\baselineskip0pt
\halign{\hjust to 8pc{\hfill$\dispstyle #$\9}⊗\hskip 6pt\hjust to 192pt{\¬#\¬\hfill}
\hskip 6pt⊗\hjust to 4pc{\9#\hfill}\cr
\blackslug⊗end of algorithm, program, or proof⊗1.1\cr\\
A↓n⊗the $n$th element of linear array $A$\cr\\
A↓{mn}⊗\+{the element in row $m$ and column $n$ of rectangular array $A$}\cr\\
A[n]⊗equivalent to $A↓n$⊗1.1\cr\\
A[m,n]⊗equivalent to $A↓{mn}$⊗1.1\cr\\
V←E⊗give variable $V$ the value of expression $E$⊗1.1\cr\\
U↔V⊗interchange the values of variables $U$ and $V$⊗1.1\cr\\
(B\→E;\;E↑\prime)⊗\+{conditional expression:\xskip denotes $E$ if $B$ is true,
$E↑\prime$ if $B$ is false}⊗\∨{8.1}\cr\\
\delta↓{kj}⊗Kronecker delta:\xskip$j=k\→1;\;0)$⊗1.2.6\cr\\
\chop to 12pt{\sum↓{R(k)}f(k)}⊗\+{sum of all $f(k)$ such that the var\-iable 
$k$ is an integer and
relation $R(k)$ is true}⊗\∨{1.2.3}\cr\\
\chop to 12pt{\prod↓{R(k)}f(k)}⊗\+{product of all $f(k)$ such that the var\-iable 
$k$ is an integer
and relation $R(k)$ is true}⊗\∨{1.2.3}\cr\\
\chop to 12pt{\min↓{R(k)}f(k)}⊗\+{minimum value of all
$f(k)$ such that the var\-iable 
$k$ is an integer and relation $R(k)$ is true}⊗\∨{1.2.3}\cr\\
\chop to 12pt{\max↓{R(k)}f(k)}⊗\+{maximum value of all
$f(k)$ such that the var\-iable 
$k$ is an integer and relation $R(k)$ is true}⊗\∨{1.2.3}\cr\\
}}  % finish the \halign and the \vjust
\eject % eject the previous page
\hjust to size{\hskip 8pc\vrule height 45pc\hfill\vrule\hskip 4pc}
\penalty1000\vskip-45pc
\vjust to 45pc{
\hjust to size{\bf\hfill\hjust to 4pc{\9\ctr{Section}}}
\hjust to size{\bf\hjust to 8pc{\ctr{Formal symbolism}\9}\hfill
Meaning\hfill\hjust to 4pc{\9\ctr{reference}}}
\vskip3pt\hrule\vskip6pt
\baselineskip0pt
\halign{\hjust to 8pc{\hfill$\dispstyle #$\9}⊗\hskip 6pt\hjust to 192pt{\¬#\¬\hfill}
\hskip 6pt⊗\hjust to 4pc{\9#\hfill}\cr
A↑T⊗\2{transpose of rectangular array $A$:}
{A↑T[j,k]=A[j,k]}⊗\∪{1.2.3}\cr\\
x↑y⊗$x$ to the $y$ power (when $x$ is positive)⊗1.2.2\cr\\
x↑k⊗\2{$x$ to the $k$th power:}
{\chop to 9pt{\medlp k≥0\→\prod↓{0≤j<k}x;\quad 1/x↑{-k}\medrp}}⊗\∪{1.2.2}\cr\\
x↑{\overline k}⊗\2{$x$ upper $k$:}
{\chop to 9pt{\medlp k≥0\→\prod↓{0≤j<k}(x+j);\quad 1/(x+k)↑{\overline{-k}}\,
\medrp}}⊗\∪{1.2.6}\cr\\
x↑{\underline k}⊗\2{$x$ lower $k$:}
{\chop to 9pt{\medlp k≥0\→\prod↓{0≤j<k}(x-j);\quad 1/(x-k)↑{\underline{-k}}
\medrp}}⊗\∪{1.2.6}\cr\\
n!⊗$n$ factorial:\xskip$n↑{\underline n}$⊗1.2.5\cr\\
f↑\prime(x)⊗derivative of $f$ at $x$⊗1.2.9\cr\\
f↑{\prime\prime}(x)⊗second derivative of $f$ at $x$⊗1.2.10\cr\\
f↑{(n)}(x)⊗$\vtop{\baselineskip20pt
\hjust{$n$th derivative:\xskip$\biglp n=0\→f(x);\;g↑\prime(x)\bigrp$,}
\hjust to 192pt{\hfill where $g(x)=f↑{(n-1)}(x)$}}
$⊗\∪{1.2.11.2}\cr\\
H↓n↑{(x)}⊗harmonic number of order $x$:\xskip\chop to 9pt{\sum↓{1≤k≤n}1/k↑x}⊗\!
1.2.7\cr\\
H↓n⊗harmonic number:\xskip $H↓n↑{(1)}$⊗1.2.7\cr\\
F↓n⊗\2{Fibonacci number:}
{(n≤1\→n;\;F↓{n-1}+F↓{n-2})}⊗\∪{1.2.8}\cr\\
B↓n⊗Bernoulli number⊗1.2.11.2\cr\\
X\cdot Y⊗\+{dot product of vectors $X=(x↓1,\ldotss,x↓n)$ and $Y=(y↓1,\ldotss,
y↓n)$:\xskip$x↓1y↓1+\cdotss+x↓ny↓n$}\cr\\
(\ldotsm a↓1a↓0.a↓{-1}\ldotsm)↓b⊗radix-$b$ positional notation:\xskip
$\sum↓k a↓kb↑k$⊗4.1\cr\\
\vtop{\baselineskip12pt
\hjust{(min $x↓1$, ave $x↓2$,}
\hjust to 8pc{\hfill max $x↓3$, dev $x↓4$)\9}}\hskip-5pt
⊗\baselineskip12pt\lower24pt\hjust to 192pt{a random variable having minimum
value $x↓1$, average (``expected'') value $x↓2$, maximum value $x↓3$, and
standard deviation $x↓4$\¬}⊗\lower24pt\hjust{1.2.10}\cr\\
}}  % finish the \halign and the \vjust
\eject % eject the previous page
\hjust to size{\hskip 8pc\vrule height 45pc\hfill\vrule\hskip 4pc}
\penalty1000\vskip-45pc
\vjust to 45pc{
\hjust to size{\bf\hfill\hjust to 4pc{\9\ctr{Section}}}
\hjust to size{\bf\hjust to 8pc{\ctr{Formal symbolism}\9}\hfill
Meaning\hfill\hjust to 4pc{\9\ctr{reference}}}
\vskip3pt\hrule\vskip6pt
\baselineskip0pt
\halign{\hjust to 8pc{\hfill$\dispstyle #$\9}⊗\hskip 6pt\hjust to 192pt{\¬#\¬\hfill}
\hskip 6pt⊗\hjust to 4pc{\9#\hfill}\cr
\dispstyle{x\choose k}⊗binomial coefficient: $(k<0\→0;\;x↑{\underline k}/k!)$⊗\!
1.2.6\cr\\
\dispstyle{n\choose n↓1,n↓2,\ldotss,n↓m}⊗\+{multinomial coefficient (defined only
when $n=n↓1+n↓2+\cdots+n↓m$)}⊗\∨{1.2.6}\cr\\
\dispstyle{n\comb[] m}⊗\2{Stirling number of the first kind:}
{\chop to 9pt{\sum↓{0<k↓1<k↓2<\cdots<k↓{n-m}<n}k↓1k↓2\ldotsm k↓{n-m}}}⊗\∪
{1.2.6}\cr\\
\dispstyle{n\comb\{\} m}⊗\2{Stirling number of the second kind:}
{\chop to 15pt{\sum↓{1≤k↓1≤k↓2≤\cdots≤k↓{n-m}≤m}k↓1k↓2\ldotsm k↓{n-m}}}⊗\∪
{1.2.6}\cr\\
\def\bslash{\char'477 } % boldface slash (vol. 2 only)
\bslash x↓1,x↓2,\ldotss,x↓n\bslash⊗\2{continued fraction:}
{1\vcenter{\hjust{\:@\char'16}}\biglp x↓1+1/(x↓2+1/(\,\cdots+1/(x↓n)\ldotsm))\bigrp
}⊗\∪{4.5.3}\cr\\
((x))⊗sawtooth function⊗3.3.3\cr\\
|x|⊗absolute value of $x$:\xskip$(x≥0\→x;\;-x)$\cr\\
\|S\|⊗cardinal:\xskip the number of elements in set $S$\cr\\
\lfloor x\rfloor⊗floor of $x$, greatest integer function:\xskip
\chop to 6pt{\max↓{k≤x}k}⊗1.2.4\cr\\
\lceil x\rceil⊗ceiling of $x$, least integer function:\xskip
\chop to 6pt{\min↓{k≤x}k}⊗1.2.4\cr\\
\leftset a\relv R(a)\rightset⊗set of all $a$ such that the relation $R(a)$ is
true\cr\\
\{a↓1,\ldotss,a↓n\}⊗the set $\leftset a↓k\relv 1≤k≤n\rightset$\cr\\
\{x\}⊗\+{fractional part (used in contexts where a real value, not a set, is
implied):\xskip$x-\lfloor x\rfloor$}⊗\∨{3.3.3}\cr\\
[y,z)⊗half-open interval:\xskip$\leftset x\relv y≤x<z\rightset$\cr\\
\langle X↓n\rangle⊗\+{the infinite sequence $X↓0$, $X↓1$, $X↓2$, $\ldots$ (here the
letter $n$ is part of the symbolism)}⊗\∨{1.2.9}\cr\\
\log↓b x⊗\+{logarithm, base $b$, of $x$ (real positive $x$ and $b$, where
$b≠1$):\xskip the $y$ such that $x=b↑y$}⊗\∨{1.2.2}\cr\\
\lg x⊗binary logarithm:\xskip$\log↓2 x$⊗1.2.2\cr\\
\ln x⊗natural logarithm:\xskip$\log↓e x$⊗1.2.2\cr\\
}}  % finish the \halign and the \vjust
\eject % eject the previous page
\hjust to size{\hskip 8pc\vrule height 45pc\hfill\vrule\hskip 4pc}
\penalty1000\vskip-45pc
\vjust to 45pc{
\hjust to size{\bf\hfill\hjust to 4pc{\9\ctr{Section}}}
\hjust to size{\bf\hjust to 8pc{\ctr{Formal symbolism}\9}\hfill
Meaning\hfill\hjust to 4pc{\9\ctr{reference}}}
\vskip3pt\hrule\vskip6pt
\baselineskip0pt
\halign{\hjust to 8pc{\hfill$\dispstyle #$\9}⊗\hskip 6pt\hjust to 192pt{\¬#\¬\hfill}
\hskip 6pt⊗\hjust to 4pc{\9#\hfill}\cr
\exp x⊗exponential of $x$:\xskip$e↑x$⊗1.2.2\cr\\
x\mod y⊗mod function:\xskip$\biglp y=0\→x;\;x-y\lfloor x/y\rfloor\bigrp$⊗1.2.4\cr\\
u(x)\mod v(x)⊗\+{remainder of polynomial $u$ after division by polynomial $v$}⊗\∨
{4.6.1}\cr\\
x≡y\modulo z⊗relation of congruence:\xskip$x\mod z=y\mod z$⊗1.2.4\cr\\
j\rslash k⊗$j$ divides $k$:\xskip$k\mod j=0$⊗1.2.4\cr\\
\hjust{B}(x,y)⊗beta function⊗1.2.6\cr\\
\gamma⊗Euler's constant:\xskip$\lim↓{n→∞}(H↓n-\ln n)$⊗1.2.7\cr\\
\gamma(x,y)⊗incomplete gamma function⊗1.2.11.3\cr\\
\Gamma(x)⊗gamma function:\xskip$\lim↓{y→∞}\gamma(x,y)$⊗1.2.5\cr\\
\delta(x)⊗characteristic function of the integers⊗3.3.3\cr\\
e⊗base of natural logarithms:\xskip$\sum↓{n≥0}1/n!$⊗1.2.2\cr\\
\zeta(x)⊗zeta function:\xskip$\lim↓{n→∞}H↓n↑{(x)}$ (when $x>1$)⊗1.2.7\cr\\
\lscr(u)⊗leading coefficient of polynomial $u$⊗4.6\cr\\
l(n)⊗length of shortest addition chain for $n$⊗4.6.3\cr\\
\Lambdait(n)⊗von Mangoldt's function⊗4.5.3\cr\\
\mu(n)⊗M\"obius function⊗4.5.2\cr\\
O\biglp f(n)\bigrp⊗big-oh of $f(n)$, as the variable $n→∞$⊗1.2.11.1\cr\\
O\biglp f(x)\bigrp⊗\+{big-oh of $f(x)$, for small values of the var\-iable $x$ (or 
for $x$ in some specified range)}⊗\∨{1.2.11.1}\cr\\
\varphi(n)⊗Euler's totient function:\xskip\chop to 18pt{\sum↓{\scriptstyle0≤k<n
\atop\scriptstyle\gcd(k,n)=1}1}⊗1.2.4\cr\\
π⊗circle ratio:\xskip$\sum↓{n≥0}\,(-1)↑n/(2n+1)$\cr\\
\phi⊗golden ratio:\xskip${1\over2}\biglp 1+\sqrt 5\,\bigrp$⊗1.2.8\cr\\
\emptyset⊗empty set:\xskip$\leftset x\relv 0=1\rightset$\cr\\
∞⊗infinity:\xskip larger than any number\cr\\
}}  % finish the \halign and the \vjust
\eject % eject the previous page
\hjust to size{\hskip 8pc\vrule height 45pc\hfill\vrule\hskip 4pc}
\penalty1000\vskip-45pc
\vjust to 45pc{
\hjust to size{\bf\hfill\hjust to 4pc{\9\ctr{Section}}}
\hjust to size{\bf\hjust to 8pc{\ctr{Formal symbolism}\9}\hfill
Meaning\hfill\hjust to 4pc{\9\ctr{reference}}}
\vskip3pt\hrule\vskip6pt
\baselineskip0pt
\halign{\hjust to 8pc{\hfill$\dispstyle #$\9}⊗\hskip 6pt\hjust to 192pt{\¬#\¬\hfill}
\hskip 6pt⊗\hjust to 4pc{\9#\hfill}\cr
\det(A)⊗determinant of square matrix $A$⊗1.2.3\cr\\
\gcd(j,k)⊗\2{greatest common divisor of $j$ and $k$:}
{\chop to 9pt{\medlp j=k=0\→0;\;\max↓{d\rslash j,\,d\rslash k}d\medrp
}}⊗\∪{4.5.2}\cr\\
\lcm(j,k)⊗\2{least common multiple of $j$ and $k$:}
{\chop to 9pt{\medlp j=k=0\→0;\;\min↓{d>0,\,
j\rslash d,\,k\rslash d}d\medrp}}⊗\∪{4.5.2}\cr\\
\hjust{sign}(x)⊗sign of $x$:\xskip$\biglp x=0\→0;\;x/|x|\bigrp$\cr\\
\Pr\biglp S(n)\bigrp⊗\baselineskip12pt
\lower24pt\hjust to 192pt{probability that statement $S(n)$
is true, for ``random'' integers $n$ (here the letter $n$ is part of the
symbolism)\¬}⊗\lower24pt\hjust to 4pc{3.5, 4.2.4\hskip0pt plus10000pt minus10000pt
}\hskip-5pt\cr\\
\hjust{mean}(g)⊗\+{mean value of the probability distribution rep\-re\-sented by
generating function $g$:\xskip $g↑\prime(1)$}⊗\∨{1.2.10}\cr\\
\hjust{var}(g)⊗$\vtop{\baselineskip26pt
\hjust{\+{variance of the probability distribution rep\-re\-sented by generating
function $g$:}}
\hjust to 192pt{\ctr{$\dispstyle
g↑{\prime\prime}(1)+g↑\prime(1)-g↑\prime(1)↑2$}}}$⊗\lower26pt\hjust{1.2.10}\cr\\
\hjust{deg}(u)⊗degree of polynomial $u$⊗4.6\cr\\
\hjust{cont}(u)⊗content of polynomial $u$⊗4.6.1\cr\\
\hjust{pp}\biglp u(x)\bigrp⊗primitive part of polynomial $u$⊗4.6.1\cr\\
\real(w)⊗real part of complex number $w$\cr\\
\imag(w)⊗imaginary part of complex number $w$\cr\\
\overline w⊗complex conjugate:\xskip$\real(w)-\imag(w)i$\cr\\
\.{\char'40}⊗one blank space⊗1.3.1\cr\\
\rA⊗register A (accumulator) of \MIX⊗1.3.1\cr\\
\rX⊗register X (extension) of \MIX⊗1.3.1\cr\\
\rI1,\ldotss,\rI6⊗(index) registers I1, $\ldotss$, I6 of \MIX⊗1.3.1\cr\\
\hjust{rJ}⊗(jump) register J of \MIX⊗1.3.1\cr\\
\.{(L:R)}⊗partial field of \MIX\ word, $0≤\.L≤\.R≤5$⊗1.3.1\cr\\
\.{OP ADDRESS,I(F)}⊗notation for \MIX\ instruction⊗1.3.1, 1.3.2\hskip-3pt\cr\\
u⊗unit of time in \MIX⊗1.3.1\cr\\
\.*⊗``self'' in \.{MIXAL}⊗1.3.2\cr\\
\hjust to 8pc{\hfill\.{0F}, \.{1F}, \.{2F}, $\ldotss$, \.{9F}\9}\hskip-5pt
⊗``forward'' local symbol in \.{MIXAL}⊗1.3.2\cr\\
\hjust to 8pc{\hfill\.{0B}, \.{1B}, \.{2B}, $\ldotss$, \.{9B}\9}\hskip-5pt
⊗``backward'' local symbol in \.{MIXAL}⊗1.3.2\cr\\
\hjust to 8pc{\hfill\.{0H}, \.{1H}, \.{2H}, $\ldotss$, \.{9H}\9}\hskip-5pt
⊗``here'' local symbol in \.{MIXAL}⊗1.3.2\cr\\
}}  % finish the \halign and the \vjust
\eject
\setcount0 801
\runninglefthead{ANSWERS TO EXERCISES---FIRST PROOFS $\copyright$ 1978}
\runningrighthead{ANSWERS TO EXERCISES---FIRST PROOFS $\copyright$ 1978}
\section{4.x}
\ninepoint